package kyssion.leetcode.num51_100;

public class code55_跳跃游戏 {

    public static void main(String[] args) {
        System.out.println(new code55_跳跃游戏().canJump2(
                new int[]{
                        3, 2, 1, 1, 4
                }
        ));
    }

    /**
     * 一个基本的想法
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        int maxRight = nums[0];
        int nowIndex = 0;
        while (nowIndex <= maxRight) {
            maxRight = Math.max(nums[nowIndex] + nowIndex, maxRight);
            if (maxRight >= nums.length - 1) {
                return true;
            }
            nowIndex++;
        }
        return false;
    }

    /**
     * 使用特殊值 0 判断之前的数据是否有能力超过0的位置
     *
     * @param nums
     * @return
     */
    public boolean canJump2(int[] nums) {
        int speed = -1;
        for (int index = nums.length - 2; index >= 0; index--) {
            if (nums[index] == 0 && speed == -1) {
                speed = 0;
            }

            if (speed != -1 && nums[index] <= speed) {
                speed++;
            } else {
                speed = -1;
            }
        }
        return speed == -1;
    }

    /**
     * 一种递归化简的思想
     * 如果上限是x 我们需要保证当前位置 为i的时候 x-i<=nums[i] 就表示如果能勾到
     * 上限x 表示的意义就是从x开始到结尾都可以实现调到最后
     * @param nums
     * @return
     */
    public boolean canJump3(int[] nums) {
        int length = nums.length, minEnd = length - 1;
        for (int i = minEnd; i >= 0; i--) {
            if (nums[i] >= (minEnd - i)) {
                minEnd = i;
            }
        }
        return minEnd == 0;
    }
}
